package leetcode

import kotlinetc.println

//https://leetcode.com/problems/sort-colors/

/**
Given an sort.getArray with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the sort.getArray counting number of 0's, 1's, and 2's, then overwrite sort.getArray with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?
 */
fun main(args: Array<String>) {


    val nums = intArrayOf(2, 0, 2, 1, 1, 0)
    sortColors1(nums)
    nums.asList().println()

//    colorsArr(3,1,0).toList().println()

}


/**
题目要求一次遍历，并且要求常数空间复杂度，一般来说是不可以的，但是这里是个特列，因为只有三种情况，0，1，2
所以还是可以根据 0.1.2 的数量不断更新最近三个数
 */

fun sortColors(nums: IntArray): Unit {

    /*var zeroCount = 0
    var oneCount = 0
    var twoCount = 0

    nums.forEachIndexed { index, it ->

        when (it) {
            0 -> zeroCount++
            1 -> oneCount++
            else -> twoCount++
        }

        val head = index - 2
        val mid = index - 1
        val tail = index

        val arr = colorsArr(zeroCount, oneCount, twoCount)
        if (tail >= 0) nums[tail] = arr[2]
        if (mid >= 0) nums[mid] = arr[1]
        if (head >= 0) nums[head] = arr[0]

    }
*/

}

/**
 * calculate what color should be placed in the last three pos given certain color count
 *
 *
 */
fun colorsArr(red: Int, white: Int, blue: Int): IntArray {

    val res = IntArray(3, { 0 })

    //for blue

    val redCount = if (red >= 3) 3 else red

    val whiteCount = if (white >= 3) 3 else white

    val blueCount = if (blue >= 3) 3 else blue


    for (i in 0 until blueCount) res[3 - i - 1] = 2


    //for white
    val b = Math.min(whiteCount, 3 - blueCount)

    for (i in 0 until b) res[3 - blueCount - i - 1] = 1


    //for red
    val c = Math.min(redCount, 3 - blueCount - b)

    for (i in 0 until c) res[3 - blueCount - b - i - 1] = 0

    return res
}

//classic
/**
 * 三个标记记录当前 red white blue 的坐标，如果出现对应的颜色，对应的坐标+1并且设置成对应的颜色，同时后面的颜色也会后移
 */
fun sortColors1(A: IntArray) {

    var i = -1
    var j = -1
    var k = -1

    for (p in 0 until A.size) {
        when {
            A[p] == 0 -> {
                A[++k] = 2
                A[++j] = 1
                A[++i] = 0
            }
            A[p] == 1 -> {
                A[++k] = 2
                A[++j] = 1

            }
            A[p] == 2 -> A[++k] = 2
        }
    }
}

